import javafx.util.Pair;

import java.util.*;

/**
* @description: 周赛309 t4
* @author hewei
* @date 2022/9/4 11:16
* @version 1.0
*/

public class MostBooked {

    public static void main(String[] args) {
        int[][] nums = {{19,20},{14,15},{13,14},{11,20}};
        MostBooked mostBooked = new MostBooked();
        System.out.println(mostBooked.mostBooked(4, nums));
    }

    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, Comparator.comparingInt(a -> a[0]));
        TreeSet<Integer> heap = new TreeSet<>();
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            heap.add(i);
        }
        PriorityQueue<Pair<Long, Integer>> haveUsed = new PriorityQueue<>(
                (a, b) -> Objects.equals(a.getKey(), b.getKey()) ?
                        Integer.compare(a.getValue(), b.getValue()) : Long.compare(a.getKey(), b.getKey()));
        for (int[] meeting : meetings) {
            long start = meeting[0];
            long end = meeting[1];
            while (!haveUsed.isEmpty() && haveUsed.peek().getKey() <= start) {
                Pair<Long, Integer> poll = haveUsed.poll();
                heap.add(poll.getValue());
            }
            if (!heap.isEmpty()) {
                Integer first = heap.pollFirst();
                haveUsed.add(new Pair<>((long) end, first));
                count[first]++;
            } else {
                Pair<Long, Integer> poll = haveUsed.poll();
                count[poll.getValue()]++;
                haveUsed.add(new Pair<>(poll.getKey() - start + end, poll.getValue()));
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (count[ans] < count[i]) ans = i;
        }
        return ans;
    }
}
